package algorithm.bin_tree.depthtraverse;

import algorithm.bin_tree.BinTree;
import algorithm.bin_tree.Node;

import java.util.List;
import java.util.Stack;

/**
 * @program: util
 * @description: 二叉树深度遍历
 * 深度遍历使用堆栈
 * @author: zhouliangliang
 * @create: 2021-06-03 20:58
 **/
public class PreRootDepthTraverse {

    /**
     * 非递归，使用堆栈的先根遍历
     * 头结点先入栈，之后右孩子先入栈，左孩子后入栈
     * @param root
     */
    private void preRootTraverseUseStack(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);//头结点入栈
        while (!stack.empty()) {
            //头结点出栈
            Node node = stack.pop();
            //输出头结点信息
            System.out.println(node.data);

            if(node.rightChild != null) {
                stack.push(node.rightChild);
            }

            if(node.leftChild != null) {
                stack.push(node.leftChild);
            }
        }
    }

    /**
     * 递归先根遍历
     * @param
     */
    private void preRootRecursion(Node root) {
        if(root == null) {
            return;
        }
        System.out.println(root.data);
        if(root.leftChild != null) {
            preRootRecursion(root.leftChild);
        }

        if(root.rightChild != null) {
            preRootRecursion(root.rightChild);
        }
    }

    public static void main(String[] args) {
        BinTree tree = new BinTree();
        int[] array = new int[]{1,2,3,4,5,6,7};
        List<Node> list = tree.createBinTree(array);
        PreRootDepthTraverse td = new PreRootDepthTraverse();
        td.preRootTraverseUseStack(list.get(0));
        td.preRootRecursion(list.get(0));
    }

}
